
\section{Analysis of Uniform-Cost Structures}

In considering the uniform-$\alpha$ group, we noticed a number of recurring structures which we will analyze below for general size (and other aspects when applicable). We will pay particular attention to the following aspects of those special structures:

\textbf{Density.} We have defined the density of a graph $G$ as the \emph{average degree} of the nodes in $G$. Theorem \ref{densitythm} identifies stable structures for various density ranges. We will list the density $d$ of each structure.

\textbf{Utility} We will discuss the utility function $u_x$ for every node $x$ for each structure.

\textbf{Conditions for stability: defining the stable $\alpha$ range.} First, we define $\Delta_{x\stackrel{+}{\rightarrow}y}$ [or $\Delta_{x\stackrel{-}{\rightarrow}y}$] to be the change in value for the node $x$ due to edge construction [or  destruction] of the edge $(x, y)$. Note that, since edges can only be added by the agreement of both nodes, we need to consider $\eadd{x}{y}$ and $\eadd{y}{x}$ together. For removal, $\erem{x}{y}$ and $\erem{y}{x}$ can be treated separately. In general, the stable $\alpha$ range will have lower and upper bounds that can be generalized as follows:

\textsc{the Lower Bound} is the maximum over all edges $(x, y)$ in $G$ of the minimum change in value due to adding $(x, y)$ over the two nodes $x$ and $y$. In other words, for every possible edge that can be added, we take the minimum $\Delta v$, then take the maximum of those. An edge will be added (the graph is unstable) as long as there is any pair where the payoff from adding the edge is higher than the cost for both members of the pair.

\textsc{the Upper Bound} is the minimum over all edges $(x, y)$ in $G$ of the change in value for $x$ and $y$ due to removing $(x, y)$. An edge will be removed (the graph is unstable) as long as there is any node whose loss from removing any incident edge is lower than the cost he would no longer be paying after removal.

\subsection{The Empty Graph}
\begin{figure}[H]
  \center
  \begin{tikzpicture}
    \foreach \i in {0,...,8}
    {
      \path (90+45*\i:14mm) node (\i) [normalnode] {};
    }
  \end{tikzpicture}
  \caption{An empty graph.\label{fig:empty_example}}
\end{figure}

The edge set of this graph on $n$ nodes is empty.

$$ d = 0 $$

\subsubsection{Utility}

All nodes are essentially equivalent. We can call a generic node $b$. 

\begin{eqnarray*}
u_b & = & 0 \\
\end{eqnarray*}

\subsubsection{Stability}
The only possible kind of edge that can be constructed is one connecting any two $b$-equivalent nodes. As there are no edges to remove, there is also no upper bound on stability.

The change in value for any node from forming an edge is

\begin{eqnarray*}
\eadd{b}{b} & = & \frac{1}{2} \\
\end{eqnarray*}

Empty graphs are stable when

$$ \frac{1}{2} \geq \alpha $$

\subsection{Line}
\label{linesection}
These are graphs where every node is connected in a single path. 

$$ d= \frac{2n - 2}{n} $$

\subsubsection{Utility}

In this structure, the utility of nodes depends on where they fall on the line. We can differentiate them based on a position $p$ away from the endpoint. For example, the endpoint is at position $p=1$, and the midpoint is at position $p=\frac{n}{2}$. $u_1$ is the same as $u_n$.

\begin{eqnarray*}
u_1 & = &\bigH_n -1 -\alpha\\
p>1, u_p & = & {\sum_{i=1}^{p} \sum_{j=p}^n \frac{1}{j-i+1}} -1 - 2\alpha \\
\end{eqnarray*}


\subsubsection{Stability}

The endpoint at $p=1$ can add an edge to any other node on the line. We consider an edge to $p=n$, the other endpoint. This is because if $p=1$ and $p=n$ will form an edge at some $\alpha$ we know that the graph is unstable at that $\alpha$ and any lower $\alpha$. Considering other edges might allow us to tighten this bound, but this is unnecessary for large $n$. We also list the value change for node $p = 1$ from dropping the edge $(1, 2)$.

\begin{eqnarray*}
\eadd{1}{n} & = & - (\frac{n+1}{2} - \bigH_n) \\
\erem{1}{2} & = & - (\bigH_n - 1) \\
\end{eqnarray*}

A line would be stable for any $\alpha$ in this range:

$$\frac{n+1}{2} - \bigH_n\ \leq \alpha \leq \bigH_n - 1$$

Since, for large $n$, there are no such $\alpha$, a line on $n$ nodes is never stable for large $n$.


%TODO prove the CUTOFF for the line!!!!

%\begin{eqnarray*}
%\frac{n+1}{2} - H_n & \leq  \alpha  \leq & H_n - 1 \\
%n+3 & \leq  \alpha  \leq & 4H_n \\
%\end{eqnarray*}
%For $n\geq 8 $, $n+3 > 4H_n$.

\subsection{Ring}
\label{ringsection}
\begin{figure}[H]
  \center
  \begin{tikzpicture}
    \foreach \i in {1,...,8}
    {
      \path (90+45*\i:14mm) node (\i) [normalnode] {};
    }
    
    \draw (1) -- (2) -- (3) -- (4) -- (5) -- (6) -- (7) -- (8) -- (1);
  \end{tikzpicture}
  \caption{A 8-node ring.\label{fig:ring_example}}
\end{figure}

This is a network with $n$ nodes, each of which has degree 2, connected in one $n$-length cycle.

$$ d= 2$$

\subsubsection{Utility}

Since every connected pair of nodes adds a total value of 1 to the network, the combined value of all pairs on $n$ nodes is ${n \choose 2} =  \frac{n(n-1)}{2}$. Since every node in a ring is equivalent, each node receives the same value. So, we divide the total value by $n$ to get the value for each node $a$.

\begin{eqnarray*}
 u_a & = & \frac{n+1}{2} - 2\alpha \\
\end{eqnarray*}


\subsubsection{Stability}
Rings are unstable for all $\alpha$ when $n$ is large. Let us consider some node $a$ on a ring of size $n$.
If $a$ drops an edge to neighbor $b$, the graph will become a line. $a$ and $b$ will become the endpoints of the new line. As was shown in section \ref{linesection}, the value of the end node on a line is:

\[u_{end}= \bigH_n - 1 - \alpha \]

So $a$ will drop an edge whenever its current utility is less than $u_{end}$, or

\[\frac{n-1}{2}-2\alpha < \bigH_n - 1 - \alpha\]

Or, more generally, no edges will be dropped when

\[\alpha \leq \frac{n+1}{2} - \bigH_n\]

%and we found an expression for this scenario in the previous subsection: $u_{(-)}=H_n - 1 - \alpha$. % TODO: give the alpha bound here ISNT THIS ALREADY DONE?

The node $a$ has $n-3$ nodes it is not connected to, and it could add an edge to any of these. However we only need to consider one possible connection -- from $a$ to a node $b$ on the opposite side of the ring. This is sufficient because if $a$ and $b$ will form an edge at some $\alpha$ we know that the graph is unstable at that $\alpha$ and any lower $\alpha$. Examining other edges might allow us to tighten this bound, but this is unnecessary for large $n$.

%Finding the utility of a node that agrees to add an edge is more difficult, as any node can potentially add an edge to any other node in the ring (except, of course, the two nodes who are already its neighbors). The new utility is determined by which new edge the node chooses to form. However, we can simplify the situation considerably by only looking at the possible edge addition that would maximize a particular node's utility.

%Later, we will rigorously show which edge this is, 
%First it's worth considering the issue intuitively. This new edge will result in an in value of $\frac{1}{2}$ for $A$ from the direct connection to $B$, but the edge also provide additional value when it shortens the shortest paths to other nodes in the graph. Since the value from the direct connection is constant, maximizing the number of nodes whose paths are shortened by an edge suffices to find the edge that gives the maximum change in value. In a ring, this means that the best node for any node $v$ to connect to would be the node that is most distant from $v$. (We call this node the node that is \emph{opposite} $v$, as when the ring graph is drawn as a circle with even spacing between the nodes, this node appears on the opposite side from $v$.)

% \medskip
In calculating the change in value for $a$ from adding $(a, b)$, we found it helpful to divide the ring into four quadrants ($A$, $B$, $C$, and $D$). Quadrants $A$ and $C$ are on one side of the new edge, and $B$ and $D$ are on the other side.
%, $|A| = |C|$ and $|B| = |D|$. This is false

If we index the nodes in the ring from $0$ to $n-1$, and denote each node in the ring as $a_{i}$ (where $i$ is the index), we can define these quadrants more rigorously. Note that the node $a$ could now be called $a_0$ and that $b$ is $a_{\frac{n}{2}}$.

%TODO: note that we are constraining graphs to have a number of nodes that is a multiple of 4

\begin{eqnarray*}
       A & = & \{v_{i}\ |\ 0 < i < \frac{n}{4} \} \\
       B & = & \{v_{i}\ |\ \frac{3n}{4} < i < n \} \\
       C & = & \{v_{i}\ |\ \frac{n}{4} < i \leq \frac{n}{2} \} \\
       D & = & \{v_{i}\ |\ \frac{n}{2} \leq i < \frac{3n}{4} \} \\
\end{eqnarray*}

(Visually, this indexing makes sense if you draw the ring as a circle, begin numbering at the top, and move counter-clockwise.)

Let us consider the utility of $a$ on this new graph $\phi$. It lies between quadrants $A$ and $B$. We do not include $a$ or the nodes between $A$ and $C$ or $B$ and $D$ in any quadrant, but we include $b$, which borders $C$ and $D$, in both $C$ and $D$.

The value of $a$ when the edge across the ring is added is made up of five major parts:

\begin{enumerate}
\item There is a set of shortest paths whose endpoints are nodes in $A$ nodes in $B$. The set of these pairs will be called $AB$.
\item There are shortest paths from nodes in $A$ to nodes in $D$ that cross through the new edge. The set of these pairs is called $AD$. There is a symmetric set $BC$.
\item There are two rings roughly half the size of the original ring. The sets of pairs in those respective rings are called $AC$ and $BD$.
\end{enumerate}

We will find the value contributed by each of these sets of pairs (while being careful to not double-count). This will allow us to find a lower bound for $\alpha$.

\subsubsection*{$AB$}

The node $a$ is in the middle of the path made up by $A \cup B$. 
The total length of this path is $\floor{\frac{n}{2} - 1}$. 
Since we are finding a lower bound for the value of $\alpha$, we can ignore part of the actual value contributed by this path. 
We only need to consider the value contributed by pairs with shortest path length less than half the total path-length. 
For all distances $l \in \mathbb{Z}$, where $1 < l < \frac{\frac{n}{2} - 1}{2}$, there are $l$ different pairs with a shortest path of $l$ nodes and that include $a$ in their path. 
Therefore, every set of pairs with a shortest path of $l$ nodes contributes a value of 1 to $a$. 
Since there are $\floor{\frac{\frac{n}{2} - 1}{2} = \frac{n}{4} - \frac{1}{2}}$ different $l$, and we must subtract one for the path of one node, they collectively contribute $\frac{n}{4} - \frac{3}{2}$.

Since this quantity includes pairs that begin or end with node $a$, and those don't belong to $AB$ because they are counted in $AC$ or $BD$, we have to remove this value. 
In $A$ there are $\frac{n}{4} - 1$ nodes, each of which contributed $1/i$ to $a$ where $i$ is the number of nodes on the path. This sum is: $\bigH_{\lfloor \frac{n}{4} - 1 \rfloor} - 1$. We need to subtract two of these from the value obtained above for the nodes in $A$ and $B$.

Thus the value from the nodes in $A$ to the nodes in $B$ is:
\[v_{AB} > \frac{n}{4} - \frac{3}{2} - 2(\bigH_{\lfloor \frac{n}{4} - 1 \rfloor} - 1)\]

\subsubsection*{$AD$}
The node $a$ is very close to the middle of the path formed by $A
\cup D$. It is not in the exact middle: there are $\frac{n}{4}-1$
nodes to the left of $a$ and $\frac{n}{4}$ nodes to the right. If
we ignore the extra node on the right, we will have a path where
$a$ is in the middle, and we will get less value than $a$
actually gets. There are $2(\frac{n}{4} - 1) + 1 = \frac{n}{2} - 1$
nodes on the path.

This is the same configuration as for $AB$, so the node gets 

$$v_{AD} > \frac{n}{4} - \frac{1}{2} - 2(\bigH_{\lfloor \frac{n}{4}-1 \rfloor} - 1)$$

\subsubsection*{$BC$}

This set is symmetrical to the $AD$ set, so the value is identical.
$$v_{BC} = v_{AD}$$

\subsubsection*{$AC$}

This set describes a ring on $\lfloor \frac{n}{2} + 1 \rfloor$ nodes. From the
formula for the utility of a node on a general ring, we know that
$a$ is getting
$$v_{AC} > \frac{\lfloor \frac{n}{2} + 1 \rfloor - 1}{2} = \frac{n}{4}$$

\subsubsection*{$BD$}

$BD$ will provide the same utility as $AC$. However, the two of these
sets combined duplicates the value given by the pair between
$a$ and $b$. So, we say that the value from $BD$ is
$$v_{BD} > v_{AC} - \frac{1}{2}$$

Therefore we know that the value of $a$ with the $(a, b)$ edge is

\[v_a > 3[\frac{n}{4} - \frac{3}{2} - 2(\bigH_{\lfloor \frac{n}{4} - 1 \rfloor} - 1)] + \frac{n}{4} + \frac{n}{4} - \frac{1}{2}\]

If we subtract the original value, we get the change in value

\[ \eadd{a}{b} = v_a - \frac{n-1}{c} > \frac{3n-2}{4} - 6\bigH_{\lfloor \frac{n}{4} - 1 \rfloor} \]

%or:
%\[u_a > \frac{5n-4}{4} - 6\bigH_{\lfloor \frac{n}{4} - 1 \rfloor} - 3\alpha \]

%Thus an edge will \emph{not} form from $a$ to $b$ whenever:
%\[\frac{n-1}{2}-2\alpha \geq \frac{5n-4}{4} - 6\bigH_{\lfloor \frac{n}{4} - 1 \rfloor} - 3\alpha \]
%or when:
%\[ \alpha \geq \frac{3n-2}{4} - 6\bigH_{\lfloor \frac{n}{4} - 1 \rfloor} \]

A ring on $n$ nodes is stable when it will neither add nor subtract edges, or when

\[ \frac{3n-2}{4} - 6\bigH_{\lfloor \frac{n}{4} - 1 \rfloor} \leq \alpha \leq \frac{n+1}{2} - \bigH_n\]

For large $n$ no $\alpha$ exists between these bounds, so rings are unstable for large $n$.


\subsection{Star}

\begin{figure}[H]
  \center
  \begin{tikzpicture}
    \path (0:0) node (center) [focusnode] {c};
    \foreach \i in {0,...,8}
    {
      \path (90+45*\i:14mm) node (\i) [normalnode] {};
      \draw (center) -- (\i);
    }
  \end{tikzpicture}
  \caption{A 9-node star.\label{fig:star_example}}
\end{figure}

A star on $n$ nodes has a central node, $c$, and $n-1$ tail nodes $t$.

$$d = \frac{2n-2}{n}$$

\subsubsection{Utility}
%Utility of the central node $c$ for a star on $n$ nodes:
$c$ gains $\frac{n-1}{2}$ for edges to the other $n-1$ nodes. $c$ is a middle man for all pairs of other nodes, so $c$ gets $\frac{1}{3}$ for each of ${n-1 \choose 2}$ pairs. $c$ has an edge to every other nodes so its cost is: $(n-1)\alpha$.

$$u_c  =  \frac{n-1}{2} + \frac{(n-1)(n-2)}{6} - (n-1) \alpha$$

$t$ gains $\frac{1}{2}$ for its one edge and has a cost of $\alpha$ for that edge. $t$ has a shortest path containing three nodes to each of the other leaves, so it gets: $\frac{n-2}{3}$ for these pairings. Finally, $t$ is not a middle-man for any pairs.

$$u_t  =  \frac{1}{2} + \frac{n-2}{3} - \alpha$$

\subsubsection{Stability}
No edges can be added to $c$. The only other possible move involving $c$ is to drop an edge to a tail node $t$. Since removing this edge will cause $c$ and $t$ to become disconnected, both $t$ and $c$ will experience the same change in value (Corollary \ref{equalvaluecor}) %TODO insert label1!!

$$\erem{c}{t} = \erem{t}{c} = -\frac{1}{2} - \frac{n-2}{3} + \alpha $$

$t$ can add an edge to another tail node $t'$. Since all edge additions produce isomorphic graphs, we need only consider this case.

$$\eadd{t'}{t}  = \frac{1}{2}$$

Therefore the $\alpha$ bound on stability of a star on $n$ nodes is:

$$\frac{1}{6} \leq \alpha \leq \frac{1}{2} + \frac{n-2}{3}$$


\subsection{$k$-Hedgehog}

\begin{figure}[H]
  \center
  \begin{tikzpicture}
    \foreach \i in {1,...,6}
    {
      \path (90+60*\i:14mm) node (\i) [focusnode] {};
      \path (90+60*\i:25mm) node (\i') [normalnode] {};
      \draw (\i) -- (\i');
    }
    
    \draw (1) -- (2) -- (3) -- (4) -- (5) -- (6) -- (1)
      -- (5) -- (2) -- (4) -- (1) -- (3) -- (5);
    \draw (3) -- (6) -- (4);
    \draw (2) -- (6);
  \end{tikzpicture}
  \caption{A 1-hedgehog with $n=12$.\label{fig:hh_example}}
\end{figure}

We define the `hedgehog' as a structure that has some number of nodes forming a clique -- the `body' of the hedgehog -- and the rest of the nodes uniformly distributed to form 1-degree tails. For example, a $1$-hedgehog has a $K_\frac{n}{2}$ for a body. Each of the body nodes has one more edge connecting it to a degree-1 'tail` node. A $k$-hedgehog has each of the $\frac{n}{k+1}$ body nodes $b$ connected to $k$ degree-1 tails $t$.
 
$$d = \frac{\frac{n^2}{(k+1)^2}+k}{n}$$

\subsubsection{Utility}

\begin{eqnarray*}
u_t & = & \frac{1}{2} + \frac{k-1+\frac{n}{k+1}}{3} + \frac{\frac{kn}{k+1}-k}{4}\\
u_b & = & \frac{k - 1 + \frac{n}{k+1}}{2} + \frac{2k\left(\frac{n}{k+1}-1\right)}{3} + \frac{k^2\left(\frac{n}{k+1}-1\right)}{4}\\
\end{eqnarray*}

\subsubsection{Stability}

\begin{eqnarray*}
\eadd{t}{t} & = & -\frac{1}{3} + \frac{4-k}{k} + \frac{2(k-1)}{5} \\
\eadd{t}{b} & = & \frac{1}{2} + \frac{k-\frac{n}{k+1}+1}{3} + \frac{\frac{n}{k+1}+k - k\frac{n}{k+1}-2}{4} + \frac{k\left(\frac{n}{k+1}-2\right)}{5}\\
\eadd{b}{t} & = &  \frac{1}{2} + \frac{k-1}{3} + \frac{\frac{n}{k+1}-k -2}{4} + \frac{k\left(\frac{n}{k+1}-2\right)}{5}\\
\erem{b}{b} & = & - \frac{6+3k^2 +2k}{12} + \frac{k+1}{n} + \frac{2k^2 + 2k}{n+k+1} + \frac{k^3+k^2}{n+2k+2}\\
\erem{b}{t} = \erem{t}{b} & = & \frac{1}{2} + \frac{k+\frac{n}{k+1} - 2}{3} + \frac{k\left(\frac{n}{k+1} -1 \right)}{4}\\
\end{eqnarray*}

The two change in value functions $\erem{b}{b}$ and $\eadd{t}{t}$ provide a stable $\alpha$ range in terms of $n$ and $k$, as they are the result of evaluating the following expression:

$$ max \left(\Delta_{t\stackrel{+}{\rightarrow}t},min\left(\Delta_{t\stackrel{+}{\rightarrow}b},\Delta_{b\stackrel{+}{\rightarrow}t}  \right) \right) \leq \alpha \leq \ min\left( - \Delta_{b\stackrel{-}{\rightarrow}t}, - \Delta_{b\stackrel{-}{\rightarrow}b}\right) $$

The above bound for stability does not necessarily exist for any $n$ and $k$, but it can be determined quickly whether, and when, it does given the particular $n$ and $k$.

When $k=1$, for example, the hedgehog structure has a stable range when $n>6$:

$$ \frac{5}{12} \leq \alpha \leq \frac{17}{12} - \left( \frac{2}{n} + \frac{4}{n+2} + \frac{2}{n+4} \right) $$

%\subsection{Complete Bipartite Graph}
%Let us consider a complete bipartite graph $K_{a,n-a}$, where $n$ is the total number of nodes and $2\leq a\leq n-a$.
%\subsubsection{Density}
%In general, the density of $K_{a,n-a}$ is

%$$ d = \frac{2a(n-a)}{n} $$

%It is maximized when $a=\frac{n}{2}$, in which case $d = \frac{n}{2}$, and minimized when $a=1$, in which case $K_{a,n-a}$ is equivalent to the star on $n$ nodes.

%\subsubsection{Utility}
%Let us refer to the two partitions of nodes in the bipartite graph as partitions $A$ and $B$, such that $|A|=a,|B|=n-a$. We will consider the changes in utility of nodes when edges are constructed within a partition (where edge construction has the same value to both nodes involved)
%\begin{eqnarray*}
%u_a & = & \frac{n-a}{2} + \frac{(n-a)(n-a-1)}{2(a+2)} + \frac{1}{n-a+2}\\
%u_b & = & \frac{a}{2} + \frac{(a)(a-1)}{2(n-a+2)} + \frac{1}{a+2}\\
% \Delta_{a\stackrel{+}{\rightarrow}a} & = & \frac{1}{2} - \frac{1}{n-a+2}\\
% \Delta_{b\stackrel{+}{\rightarrow}b} & = & \frac{1}{2} - \frac{1}{a+2} \\
% \Delta_{a\stackrel{-}{\rightarrow}b} & = & -\frac{1}{2} + \frac{1}{n} - \frac{a-1}{n-a+2} + %\frac{a-1}{n-a+1} - \frac{n-a-1}{a+2}\\
% \Delta_{b\stackrel{-}{\rightarrow}a} & = &  -\frac{1}{2} + \frac{1}{n} - \frac{n-a-1}{a+2} + %\frac{n-a-1}{a+1} - \frac{a-1}{n-a+2}\\
%\end{eqnarray*}


%\subsubsection{Stability}

%We know that a stable $\alpha$ range is of the form

%$$ max\left(  \Delta_{a\stackrel{+}{\rightarrow}a}, \Delta_{b\stackrel{+}{\rightarrow}b}\right) \leq \alpha \leq min\left(  - \Delta_{a\stackrel{-}{\rightarrow}b}, - \Delta_{b\stackrel{-}{\rightarrow}a}\right)$$

%Since we know that $a \leq n-a$, we can say that  $\Delta_{a\stackrel{+}{\rightarrow}a}$ is the tighter lower bound, and, likewise, that  $-\Delta_{b\stackrel{-}{\rightarrow}a}$ is the tighter upper bound. So, the tight $\alpha$ range is 

%$$\frac{1}{2} - \frac{1}{n-a+2}  \leq \alpha \leq \frac{1}{2} - \frac{1}{n} + \frac{n-a-1}{a+2} - \frac{n-a-1}{a+1} + \frac{a-1}{n-a+2}$$

%\textbf{Claim:} There is a reasonable range of $\alpha$ for all $a$ and $n$ as defined.

%\begin{proof}
% Let us consider for what ranges of $n$ and $a$ it is true that the specified range makes sense:

%\begin{eqnarray*}
%\frac{1}{2} - \frac{1}{a+2} & \leq & \frac{1}{2} - \frac{1}{n} + \frac{n-a-1}{a+2} - \frac{n-a-1}{a+1} + \frac{a-1}{n-a+2} \\
%\
%\end{eqnarray*}

%[1] We know that, for all specified $a,n$, $\frac{n-a-1}{a+2}$

%[2]

%[3]
%\end{proof}

\subsection{$k$-Single-Tails}

A $k$-single-tail is a complete graph on $n-k$ nodes with $k$ of those `body' nodes connected by one edge to a single tail node such that all tail nodes are of degree exactly 1.

$$d = \frac{(n-2k)(n-k-1)+k(n-k)+k}{n} = \frac{n^2 - 2kn + k^2 - n + 3k}{n} $$

%\subsubsection{General Bounds}
%First, let us estabish that of all possible moves within the $k$-single-tail structure, the relevant move for the lower bound is the construction of the edge connecting a tail node and, if possible (ie, when $k>1$), another tail node. This is a preferable move over the one where a tail node is connected to any body node as fewest multiple shortest paths aregenerated.

\subsubsection{Utility}

Let $t$ and $t'$ be any tail nodes. Let $b$ and $b'$ be any body nodes that do not have tails attached. Let $b_t$ and $b_t'$ be any body nodes that do have tails attached.

$$u_t = \frac{1}{2} + \frac{n - k - 1}{3} + \frac{k - 1}{4} - \alpha$$

$$u_b = \frac{n - k - 1}{2} + \frac{k}{3} - (n - k) \alpha$$

$$u_{b_t} = \frac{n-k}{2} + \frac{k - 1}{3} + \frac{n - k - 1}{3} + \frac{k - 1}{4} - (n - k) \alpha$$

\subsubsection{Stability for $1<k<\frac{n}{2}$}

\begin{eqnarray*}
\eadd{t}{t'} & = & \frac{5}{12} \\
\eadd{b}{t} & = & (\frac{1}{2} - \frac{1}{3}) + (n - k - 2)(\frac{1}{4} - \frac{1}{3}) + (k - 1)(\frac{1}{5} - \frac{1}{4})\\
\eadd{t}{b} & = & (\frac{1}{2} - \frac{1}{3}) + (n - k - 2)(\frac{1}{4} - \frac{1}{3}) + (k - 1)(\frac{1}{5} - \frac{1}{4})\\
\eadd{b_t}{t} & = & \frac{1}{4} + \frac{n - k - 2}{4}\\
\eadd{t}{b_t} & = & \frac{1}{4} + (n - k - 2)(\frac{1}{4} - \frac{1}{3})\\
\erem{b_t}{b_t'} & = & (\frac{1}{n-k} - \frac{1}{2}) + 2 (\frac{1}{n - k + 1} - \frac{1}{3}) + (\frac{1}{n - k + 2} - \frac{1}{4})\\
\erem{b_t}{b} & = & -\frac{1}{2} - \frac{n - k}{3} - \frac{k}{4}\\
\erem{b}{b_t} & = & -\frac{1}{2} - \frac{n - k}{3} - \frac{k}{4}\\
\erem{b}{b'} & = & \frac{1}{n - k} - \frac{1}{2}\\
\end{eqnarray*}

In general, for $1<k<\frac{n}{2}$ $k$-single-tails are stable when

$$ \frac{5}{12} \leq \alpha \leq \frac{1}{2} - \frac{1}{n-k} $$ 

Given a particular $k$, we can find out just how large $n$ has to be before the range makes sense. For example, when $k=\frac{n}{4}$,
\begin{eqnarray*}
 \frac{1}{12} & \geq & \frac{1}{3n/4} \\
 n & \geq & 16 \\
\end{eqnarray*}

\subsubsection{Stability for $k=1$}

The only addition possible here is the construction of an edge from the tail node to one of the body nodes without a tail, so this will dictate the new lower bound.

We can say that the $1$-single-tail is stable when

$$\frac{1}{2} - \frac{1}{3} + \frac{n-3}{4} - \frac{n-2}{3} \leq \alpha \leq \frac{1}{2} - \frac{1}{n-1}$$

Which makes sense for all $n \geq 5$.

\subsubsection{Stability for $k=\frac{n}{2}$}

Note that the $\frac{n}{2}$ single-tail is equivalent to the $1$-hedgehog, which we have extensively qualified previously.

\subsection{Complete Graph}

$$ d = n-1 $$

\subsubsection{Utility}

The combined value of all nodes on a connected graph is $\frac{n(n-1)}{2}$, since every connected pair of nodes adds a total value of 1 to the network. Since the complete graph is symmetric, all nodes have the same value. So, we divide the total value by $n$ to get the value per node: $v=\frac{n-1}{2}$. Each node in a complete graph has $n-1$ neighbors, so the utility for each node is 

$$u=\frac{n-1}{2}-(n-1)\alpha$$

\subsubsection{Stability}

No nodes can be added to a complete graph, so we need only consider the removal of an edge. Consider any node $a$. If the edge from $a$ to $b$ is removed than $a$ will have only $n-2$ direct connections. $a$ has a path of length two to $b$ through any other node in the graph. All other nodes are directly connected to each other, so $a$ is never a middle man. Thus the resulting utility is:

\[u = \frac{n-2}{2} + \frac{1}{n} - (n-2)\alpha\]

So no edges are dropped when

\[\frac{n-1}{2}-(n-1)\alpha \geq \frac{n-2}{2} + \frac{1}{n} - (n-2)\alpha\]

Complete graphs are stable when

\[\alpha \leq \frac{1}{2} - \frac{1}{n} \]
